package com.waiting.leetcode;

/**
 * @Description
 * @Author bjweitingting
 * @Date 2019/3/19
 **/
public class HouseRobberII213 {
    public static void main(String[] args) {
        int[] nums = {2, 3, 2};
        System.out.println(rob(nums));
    }

    public static int rob(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        //第一个偷
        int case1 = rob(nums, 0, nums.length - 1);
        //第一个不偷，从第二个下标开始
        int case2 = rob(nums, 1, nums.length);
        return Math.max(case1, case2);
    }

    public static int rob(int[] nums, int start, int end) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int steal = nums[start], notSetal = 0;
        for (int i = start + 1; i < end; i++) {
            int tmp = steal;
            steal = Math.max(notSetal + nums[i], steal);
            notSetal = Math.max(tmp, notSetal);
        }
        return Math.max(steal, notSetal);
    }

}
